package leetcode_800;

import java.util.ArrayList;
import java.util.List;

/**
 *@author 周杨
 *LetterCasePermutation_784 一个字符串可能包含大小写字母和数字 问能把大小写转换的全部排列
 *describe:用回溯 AC 96%
 *2018年10月22日 上午9:46:24
 */
public class LetterCasePermutation_784 {
	public static void main(String[] args) {
		LetterCasePermutation_784 test=new LetterCasePermutation_784();
		List<String> res=test.letterCasePermutation("a2bC");
	}
	
	public List<String> letterCasePermutation(String S) {
        List<String> res=new ArrayList<String>();
        help(res,S.toCharArray(),0);
        return res;
    }
	
	private void help(List<String> res,char[] chars,int index) {
		if(index==chars.length) {
			String now=new String(chars);
			res.add(now);
			return ;
		}
		if(chars[index]<='z'&&chars[index]>='a') {
			chars[index]-=32;
			help(res,chars,index+1);
			chars[index]+=32;//回溯
		}
		else if(chars[index]<='Z'&&chars[index]>='A') {
			chars[index]+=32;
			help(res,chars,index+1);
			chars[index]-=32;
		}
		
		help(res, chars, index + 1);//无论如何往下走
		
	}
}
